TSP问题，贪心法，最近邻点，最短链接 |
您所在的位置：网站首页 › 链路设计 战略 › TSP问题，贪心法，最近邻点，最短链接 |
TSP问题，贪心法，最近邻点，最短链接
|
笔者接着上一次的博客继续讨论TSP问题（TSP问题,动态规划法），这次采用贪心法，至少有两种贪心策略是合理的：最近邻点策略和最短链接策略。 （一）最近邻点策略 从任意城市出发，每次在没有到过的城市中选择最近的一个，直到经过了所有的城市，最后回到出发城市。 设图G有n个顶点，边上的代价存储在二维数组w[n][n]中，集合V存储图的顶点，集合P存储经过的边，最近邻点策略求解TSP问题的算法如下： 1． P={ }; 2． V=V-{u0}; u=u0; //从顶点u0出发 3． 循环直到集合P中包含n-1条边 3.1 查找与顶点u邻接的最小代价边(u, v)并且v属于集合V； 3.2 P=P+{(u, v)}; 3.3 V=V-{v}; 3.4 u=v; //从顶点v出发继续求解 代码实现如下： #include #include const int amount = 5; int TSP1(int arc[amount][amount], int temp) { int Count_hyh= 0, TSPLen_hyh = 0; int min_hyh, u, v; int tem[amount] = {0}; u = temp; tem[temp] = 1; while (Count_hyh< amount-1) { min_hyh = 100; for (int j = 0; j < amount; j++) if ((tem[j] == 0) && (arc[u][j] != 0) && (arc[u][j] < min_hyh)) { v = j; min_hyh = arc[u][j]; } TSPLen_hyh += arc[u][v]; tem[v] = 1; Count_hyh++; cout |
【本文地址】